A wireless mesh network is a wireless cooperative communication infrastructure that is made up of a plurality of individual wireless transceivers. Each wireless transceiver in the wireless mesh network that has network routing capabilities is a network router. A mesh network client is an electronic device that is equipped with a wireless network interface card (NIC) that enables the device to be wirelessly connected to a wireless mesh router. Such an electronic device may comprise a desktop computer, a laptop computer, a personal digital assistant (PDA), a cell phone, or other similar wirelessly enabled device.
Wireless mesh networks can be integrated with other networks (e.g., the Internet) through gateway and bridging functions in the mesh routers. Mesh network clients do not have mesh functionality such as routing capacity but use a mesh network to extend the network coverage. The mesh routers in the wireless mesh network automatically establish and maintain mesh connectivity between themselves to create an ad hoc network.
The currently proposed draft standard in the IEEE 802.11 working group that sets forth the Wireless Mesh Network is IEEE P802.11s (sometimes referred to herein as the “Standard”). The full title of the currently proposed draft standard is “Draft Standard for Information Technology—Telecommunications and Information Exchange Between Systems—Local and metropolitan area networks—Specific Requirements—Part 11: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications. Amendment: Mesh Networking.
In IEEE P802.11s, any node in the mesh network that supports mesh services that control, manage and operate the mesh network is a Mesh Point (MP). If a node additionally supports access to a client station (designated STA) or a non-mesh node, it is called a Mesh Access Point (MAP). A Mesh Point Portal (MPP) is a Mesh Point that has a non-802.11 connection to an external network (e.g., the Internet). A Mesh Point Portal (MPP) serves as an entry point for Medium Access Control (MAC) Service Data Units (MSDUs) to enter the mesh network or to exit the mesh network.
The Standard defines a default routing protocol called Hybrid Wireless Mesh Protocol (HWMP). The HWMP protocol is a mesh network routing protocol that combines the flexibility of on-demand routing with an option of efficient proactive topology tree extensions for routing between a root and each Mesh Point (MP). The combination of reactive and proactive elements of the HWMP protocol enables an optimal and efficient path selection in a wide variety of mesh networks.
The HWMP protocol is based on processing rules from the Ad Hoc On Demand (AODV) routing protocol (IETF RFC 3561) adapted for Layer-2 address based routing and link metric awareness. The Ad Hoc On Demand (AODV) routing protocol forms the basis for finding on-demand routes within a mesh network. Additional protocol primitives and procedures are used to proactively set up a distance-vector tree rooting at a single root Mesh Point.
The HWMP protocol supports two modes of operation depending upon the configuration. The two modes of operation are not exclusive and both of the modes may be used concurrently.
The first mode is an “on demand” mode. The “on demand” mode allows Mesh Points in the mesh network to communication using peer-to-peer routes. The “on demand” mode is used in situations when there is no root Mesh Point configured. The “on demand” mode is also used if a root Mesh Point is configured and an “on demand” path can provide a better path to a destination in the mesh network.
The second mode is a “proactive tree building” mode or “proactive” mode. As will be more fully described, the “proactive” mode can be performed by using a Root Announcement message. The “proactive” mode can also be performed by using a proactive Path Request message. In HWMP the Path Request message is used to discover a path to one or more destinations, build a proactive (reverse) path selection tree to the root Mesh Point, and confirm a path to the destination.
The HWMP protocol modes of operation utilize common processing rules and primitives. Management messages in the HWMP protocol include the Path Request (PREQ) message, the Path Reply (PREP) message, the Path Error (PERR) message, and the Root Announcement (RANN) message. The HWMP protocol management messages are sometimes referred to as Information Elements (IE) because each HWMP management message includes the corresponding IE in it. The metric costs of the mesh network links determine which route the HWMP protocol builds. In order to propagate the metric information between the Mesh Points (MP) of the mesh network, a metric field is used in the PREQ, PREP and RANN messages. A hop count field is also included in the PREQ, PREP and RANN messages to record the hop counts that a management message goes through. A Time to Live (TTL) field is also in the PREQ, PREP and RANN messages to avoid an unlimited flooding of the PREQ, PREP and RANN messages.
Routing in the HWMP protocol also uses a sequence number mechanism to maintain loop-free connectivity at all times. Each Mesh Point maintains its own sequence number. The sequence number is propagated to other Mesh Points in the mesh network in the HWMP protocol management messages.
In the proactive mode of operation, there are two mechanisms for proactively disseminating routing information for reaching the root Mesh Point (Root MP). The first method uses a proactive Path Request (PREQ) message and creates routes between the root and all Mesh Points in the mesh network proactively. The second method uses a Root Announcement (RANN) message to distribute route information for reaching the root. The second method is sometimes referred to as the “proactive RANN” method. The actual routes to the root can be built “on demand”.
In the proactive PREQ method the PREQ tree building process begins with a proactive Path Request element sent by the root Mesh Point, with the destination address set to all ones (broadcast address). A Mesh Point hearing a proactive PREQ creates or updates its forwarding information to the root Mesh Point, updates the metric and hop count of the PREQ, records the metric and hop count to the root Mesh Point, and then transmits the updated PREQ. If the PREQ is sent with a “Proactive PREP” bit set to one (“1”), then the recipient Mesh Point will send a proactive PREP. The proactive PREP establishes the path from the root Mesh Point to the Mesh Point. When the path from a Mesh Point to a root Mesh Point changes, and the root Mesh Point PREQ was sent with a “Proactive PREP” bit set to one (“1”), then the recipient Mesh Point will send a proactive PREP to the root Mesh Point containing the addresses of the Mesh Points that have established a path to the root Mesh Point through the current Mesh Point.
In the proactive RANN method the root periodically floods a RANN message into the mesh network. The information that is contained in the RANN message is used to disseminate route metrics to the root. Upon receiving a RANN message, each Mesh Point that has to create or refresh a route to the root will send a unicast Path Request (PREQ) message to the root via the Mesh Point from which it received the RANN message. The unicast Path Request (PREQ) message follows the same processing rules as set forth for the “on demand” mode of operation.
The root sends a Path Reply (PREP) message in response to each Path Request (PREQ) message. The unicast Path Request (PREQ) message creates the reverse route from the root to the originating Mesh Point. The Path Reply (PREP) message that is sent in response creates the forward route from the Mesh Point to the root. When the route from a Mesh Point to a root changes, the root may send a Path Reply (PREP) message with the addresses of the Mesh Points that have established a route to the root through the current Mesh Point.
As previously mentioned, the proactive RANN method causes the root to periodically flood RANN messages into the mesh network. The RANN messages propagate route metric information across the mesh network so that each Mesh Point can select a best metric path to the announced root. This mechanism allows bidirectional trees to be built using a robust unicast procedure initiated by the Mesh Points. This mechanism ensures that the root is aware of all of the Mesh Points in the mesh network.
The proactive PREQ method also causes the root to periodically flood PREQ messages into the mesh network. The PREQ messages propagate route metric information across the mesh network so that each Mesh Point can select a best metric path to the announced root. This mechanism allows bidirectional trees to be built.
In a mesh network there are different kinds of multihop broadcast/multicast data/management messages (e.g., RANN messages, PREQ messages, or broadcast data messages). Each multihop broadcast/multicast message contains (in addition to other information) a value that represents a Time to Live (TTL) count. The Time to Live (TTL) count is an integer number that represents the maximum number of hops that a broadcast/multicast message is allowed to be forwarded in the mesh network. A Mesh Point that receives a broadcast/multicast message will decrement the value of the Time to Live (TTL) count in the TTL field before re-transmitting the broadcast/multicast message. If the decremented value of the TTL field is zero (0) then the broadcast/multicast message will be discarded.
The value of the Time to Live (TTL) count is set by the Mesh Point that originates the broadcast/multicast message. In the method used in the prior art the value of the Time to Live (TTL) count is set to a fixed value of two hundred fifty five (255) or a static network diameter. The Time to Live (TTL) count of two hundred fifty five (255) represents a maximum value of the static network diameter. A typical default value of the static network diameter and a typical default value of the TTL count of the broadcast/multicast message is thirty (30). A fixed TTL value of two hundred fifty five (255) or the static network diameter (typical value 30) means that an unnecessarily large number of broadcast/multicast messages will be transmitted and re-transmitted (flooded) through the mesh network.
Therefore, there is a need in the art for system and method that reduces the unnecessarily large number of broadcast/multicast messages that must be transmitted and re-transmitted through a mesh network due to the relatively large fixed value of the Time to Live (TTL) count in the broadcast/multicast messages.
Before undertaking the Detailed Description of the Invention below, it may be advantageous to set forth definitions of certain words and phrases used throughout this patent document: the terms “include” and “comprise,” as well as derivatives thereof, mean inclusion without limitation; the term “or,” is inclusive, meaning and/or; the phrases “associated with” and “associated therewith,” as well as derivatives thereof, may mean to include, be included within, interconnect with, contain, be contained within, connect to or with, couple to or with, be communicable with, cooperate with, interleave, juxtapose, be proximate to, be bound to or with, have, have a property of, or the like.
The term “controller” means any device, system, or part thereof that controls at least one operation. A controller may be implemented in hardware, software, firmware, or combination thereof. It should be noted that the functionality associated with any particular controller may be centralized or distributed, whether locally or remotely.
Definitions for certain words and phrases are provided throughout this patent document, those of ordinary skill in the art should understand that in many, if not most instances, such definitions apply to prior uses, as well as to future uses, of such defined words and phrases.